class Solution
{
public:
    int findRadius(vector<int> &houses, vector<int> &heaters)
    {
        sort(heaters.begin(), heaters.end());
        int minRadius = 0;
        for (int house : houses)
        {
            auto nearHeaterPos = upper_bound(heaters.begin(), heaters.end(), house);
            if (nearHeaterPos == heaters.end())
            {
                minRadius = max(minRadius, house - *(nearHeaterPos - 1));
            }
            else if (nearHeaterPos == heaters.begin())
            {
                minRadius = max(minRadius, *nearHeaterPos - house);
            }
            else
            {
                minRadius = max(minRadius, min(house - *(nearHeaterPos - 1), *nearHeaterPos - house));
            }
        }
        return minRadius;
    }
};